package LeetCode.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/8/5
 * @Description:53. 最大子数组和
 */
public class maximum_subarray {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] nums={-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray4(nums));
    }
    static class Solution {
        /*暴力*/
        public int maxSubArray1(int[] nums) {
            int res=-10000,t=0;
            for (int i = 0; i < nums.length ;i++) {
                t=0;
                for (int j = i; j<nums.length ; j++) {
                    t+=nums[j];
                    res=Math.max(res,t);
                }
            }
            return  res;
        }
        /*动态规划 时间On  空间On*/
        public int maxSubArray2(int[] nums) {
            int res=-10000;
            int len = nums.length;
            int []dp=new int[len];
            dp[0]=nums[0];
            for (int i = 1; i < nums.length ;i++) {
                dp[i] =Math.max(dp[i-1]+nums[i],nums[i]);
                res=Math.max(res,dp[i]);
            }
            return  res;
        }
        /*贪心时间On  空间O1*/
        public int maxSubArray3(int[] nums) {
            int res = -10000,sum=0;
            int len = nums.length;
            for (int i = 0; i < len ; i++) {
                sum+=nums[i];
                //如果全是负数，保存的会是最大的负数也不影响结果
                res=Math.max(res,sum);
                //当和为0时，从小开始计算
                if(sum<0) sum=0;
            }
            return res;
        }
        /*分治法 时间Onlogn  空间Ologn
        * 取中间，要么在左边，要么在右边，要么跨两把*/
        public int maxSubArray4(int[] nums) {
            int res = -10000,sum=0;
            int len = nums.length;
            if (len==0) return 0;
            return maxSubSum(nums,0,len-1);
        }
        private int maxCross(int[] nums,int l,int mid,int r){
            int sum=0;
            int lSum=-10000;
            int rSum=-10000;
            //计算以mid结尾左边最大子数组和
            for (int i = mid; i >=l  ; i--) {
                sum+=nums[i];
                if(sum>lSum){
                    lSum=sum;
                }
            }
            sum=0;
            //计算右边
            for (int i = mid+1; i < r; i++) {
                sum+=nums[i];
                if(sum>rSum){
                    rSum=sum;
                }
            }
            return  lSum+rSum;
        }
        //单侧
        private int maxSubSum(int[] nums,int l,int r){
            if(l==r){
                return  nums[l];
            }
            int mid=l+(r-l)/2;
            return Math.max(Math.max(maxSubSum(nums,l,mid),maxSubSum(nums,mid+1,r)) ,maxCross(nums,l,mid,r));
        }
    }
}
